1423K - Lonely Numbers - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long long int lli;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vl;
typedef vector<lli> vli;
typedef vector<double> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define res resize
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
#define lsb(x) x&(-x)

const ll MOD = 1e9 + 7;
const char nl = '\n';
const int MAX = 3e5 + 5;
const double eps = 1e-18;

void solve() {
    int tt;
    cin >> tt;

    int n = 1e6;
    vi is(n, 1);
    is[0] = is[1] = 0;
    for(int i=4; i<=n; i += 2) is[i] = 0;
    for(int i=3; i*i<=n; i+=2) {
        if(is[i]) {
            for(int j=i*i; j<=n; j+=2*i) is[j] = 0;
        }
    }

    for(int i=0; i<=n; i++) {
        is[i] += is[i-1];
    }

    while(tt--) {
        int nn;
        cin >> nn;

        int l = sqrt(nn);
        cout << is[nn] - is[l] + 1 << nl;
        
    }
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    solve();
    return 0;
}